package J.算法.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * 与567类似
 */
public class _567字符串的排列 {
    public boolean checkInclusion(String s1, String s2) {

        Map<Character,Integer> window = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();
        for (char c:s1.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }


        int left=0,right=0;
        int valid =0;

        while (right < s2.length()){

            char in = s2.charAt(right);
            right++;

            if (need.containsKey(in)){
                window.put(in,window.getOrDefault(in,0)+1);
                if (window.get(in).equals(need.get(in)) ){
                    valid++;

                }
            }

            while (right-left >= s1.length()){
                //结果判断
                if (valid == need.size()){
                    return true;
                }

                char out = s2.charAt(left);
                left++;

                if (need.containsKey(out)){
                    if (window.get(out).equals(need.get(out))){
                        valid--;
                    }
                    window.put(out,window.getOrDefault(out,1)-1);
                }

            }
        }

        return false;




    }

}
